{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CART分类树算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CART生成二叉决策树**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们知道，在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。\n",
    "\n",
    "在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。\n",
    "\n",
    "但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "子集计算基尼不纯度，即随机放置的数据项出现于错误分类中的概率。以此来评判属性对分类的重要程度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$Gini(D)=\\sum_{k=1}^Kp_k (1−p_k )=1−∑ p^2_k  $$  其中$p_k$为任一样本点属于第k类的概率，也可以说成样本数据集中属于k类的样本的比例。\n",
    "\n",
    "集合D的基尼指数为$Gini(D)$，在特征A条件下的集合D的基尼指数为\n",
    "$$Gini(D|A) = \\sum \\frac{|D_i|}{|D|}Gini(D_i)$$\n",
    "\n",
    "其中 $|D_i|$为特征A取第i个值时对应的样本个数。|D|为总样本个数\n",
    "\n",
    "CART算法中对于分类树采用的是上述的基尼指数最小化准则。对于回归树，CART采用的是平方误差最小化准则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CART树算法的剪枝**\n",
    "\n",
    "由于决策时算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，即类似于线性回归的正则化，来增加决策树的返回能力。\n",
    "\n",
    "但是，有很多的剪枝方法，我们应该怎么选择呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**CART采用的办法是后剪枝法，即先生成决策树，然后产生所有（是所有的，也就是形成了子树序列）可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "那么CART算法是如何产生一批剪枝树的呢？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "剪枝操作中的损失函数为：\n",
    "\n",
    ">损失函数=拟合度+a*模型复杂度 \n",
    "\n",
    "当a=0时，整体树为最优树，当a为无穷大时，只有根节点的树为最优树。a逐渐增大，树逐渐剪值。\n",
    "\n",
    "若$a1<a2$，则a1对应的最优树一定整体包含a2对应的最优树。也就是说最优树是嵌套的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CART算法中对于子树T的损失函数为\n",
    "\n",
    "$$C_a(T) = C(T)+a|T|$$\n",
    "\n",
    "其中$C(T)$为对训练数据的预测误差（如基尼指数），$|T|$为树的叶子节点个数，用来代表模型复杂度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "树中每个节点$t$下的树如果被减去，则整体损失函数减少的程度为\n",
    "\n",
    "$$g(t) =\\frac{C(t)-C(T_t)}{|T_t|-1} $$  其中$T_t$为以t为根节点的子树，$C(t)$为t为单节点树时的预测误差，$C(T_t)$为树$T_t$的预测误差，$|T_t|$为树$T_t$的叶子节点个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在整体树$T_0$中剪去$g(t) $最小的$T_t$得到子树$T_1$，在从$T_1$中剪去$g(t) $最小的$T_t$得到子树$T_2$，如此递归，直到只有根节点，这样就按找到了一个按顺序的子树序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最后通过交叉验证得到最优的一个子树，作为真正剪枝后的树。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
